#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

// (a[r] - a[l-1]) % k == 0 -> a[r] % k == a[l-1] % k
int subarraysDivByK(vector<int>& nums, int k) {
    int n = nums.size();
    unordered_map<int, int> m = { {0,1} };
    int res = 0, sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += nums[i];
        int t = (sum % k + k) % k;
        if (m.count(t))
            res += m[t];
        m[t]++;
    }
    return res;
}